//
// Created by vista on 2017/12/20.
//

#include <vector>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <set>
#include <iostream>
#include <cassert>
using namespace std;

class Solution {
public:
    void level(const int n,int l,int r,string pre,vector<string> & strs){
        if ( l == n && r == n - 1){
            strs.push_back(pre+')');
        }
        else if (n - l == 0){
            level(n,l,r+1,pre+')',strs);
        }
        else if (l == r){
            level(n,l+1,r,pre+'(',strs);
        }else{
            level(n,l+1,r,pre+'(',strs);
            level(n,l,r+1,pre+')',strs);
        }
    }

    vector<string> generateParenthesis(int n) {
        vector<string> strs;

        if(n == 0)
            return strs;

        level(n,0,0,"",strs);

        return strs;
    }
};

int main(){

    Solution solution;

    __uint64_t timebegin =  clock_gettime_nsec_np(CLOCK_REALTIME);

    auto s = solution.generateParenthesis(0);

    for (const auto &i : s) {
        std::cout << i << ",";
    }
    std::cout << endl;
    s = solution.generateParenthesis(1);
    for (const auto &i : s) {
        std::cout << i << ",";
    }
    std::cout << endl;
    s = solution.generateParenthesis(2);
    for (const auto &i : s) {
        std::cout << i << ",";
    }
    std::cout << endl;
    s = solution.generateParenthesis(3);
    for (const auto &i : s) {
        std::cout << i << ",";
    }
    std::cout << endl;

    __uint64_t timeend =  clock_gettime_nsec_np(CLOCK_REALTIME);

    cout << (timeend - timebegin) / 1000000.0 << endl;

    return 0;

}

